﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace CompilerForC.LexicalAnalysis
{
    /// <summary>
    /// Class used to tokenize C source code into tokens. Usage of Lexer 
    /// consists of providing lexer with source code and calling Tokenize method. 
    /// After tokenization is finished, Tables property can be used to retrieve 
    /// information about lexical elements of the provided source code.
    /// </summary>
    public class Lexer
    {
        #region Inner Types

        /// <summary>
        /// Enumerates results of the line prefix validation.
        /// </summary>
        public enum ValidationResult
        {
            Unknown,
            Keyword,
            Operator,
            Identifier,
            IntegerOctal,
            IntegerDecimal,
            IntegerHexadecimal,
            Float,
            Double,
            Character,
            String,
        }

        /// <summary>
        /// Token specific for the single source line.
        /// </summary>
        private struct LineToken
        {
            /// <summary>
            /// Validation result associated with the line token.
            /// </summary>
            public ValidationResult Result;
            /// <summary>
            /// String value that was used to classify token.
            /// </summary>
            public string Value;
            /// <summary>
            /// Start index inside the source line.
            /// </summary>
            public int Index;
            /// <summary>
            /// Line number in the source code.
            /// </summary>
            public int LineNumber;

            /// <summary>
            /// Returns unclassified token.
            /// </summary>
            public static readonly LineToken Unknown = new LineToken(ValidationResult.Unknown, String.Empty, -1, -1);

            /// <summary>
            /// Constructs and initializes line token.
            /// </summary>
            /// <param name="result">Validation result associated with the line token.</param>
            /// <param name="value">String value that was used to classify token.</param>
            /// <param name="index">Start index inside the source line.</param>
            /// <param name="lineNumber">Line number in the source code.</param>
            LineToken(ValidationResult result, string value, int index, int lineNumber)
            {
                Result = result;
                Value = value;
                Index = index;
                LineNumber = lineNumber;
            }
        }
                
        #endregion Inner Types

        #region Private Static Fields

        /// <summary>
        /// Temporary map used to quickly retrieve table index for the keyword name.
        /// </summary>
        private static Dictionary<string, int> _keywordIndexMap = new Dictionary<string, int>();
        /// <summary>
        /// Temporary map used to quickly retrieve table index for the operator name.
        /// </summary>
        private static Dictionary<string, int> _operatorIndexMap = new Dictionary<string, int>();
        /// <summary>
        /// Temporary map used to quickly retrieve table index for the identifier name.
        /// </summary>
        private static Dictionary<string, int> _identfierIndexMap = new Dictionary<string, int>();
        /// <summary>
        /// Temporary map used to quickly retrieve table index for the constant value.
        /// </summary>
        private static Dictionary<string, int> _constantIndexMap = new Dictionary<string, int>();

        /// <summary>
        /// Validates identifiers.
        /// </summary>
        private static StateMachine _identifierValidator = new StateMachine();
        /// <summary>
        /// Validates integers with octal base.
        /// </summary>
        private static StateMachine _octalIntegerValidator = new StateMachine();
        /// <summary>
        /// Validates integers with decimal base.
        /// </summary>
        private static StateMachine _decimalIntegerValidator = new StateMachine();
        /// <summary>
        /// Validates integers with hexadecimal base.
        /// </summary>
        private static StateMachine _hexadecimalIntegerValidator = new StateMachine();
        /// <summary>
        /// Validates single-precision floating-point numbers.
        /// </summary>
        private static StateMachine _floatValidator = new StateMachine();
        /// <summary>
        /// Validates double-precision floating-point numbers.
        /// </summary>
        private static StateMachine _doubleValidator = new StateMachine();
        /// <summary>
        /// Validates string literals.
        /// </summary>
        private static StateMachine _stringValidator = new StateMachine();
        /// <summary>
        /// Validates character literals.
        /// </summary>
        private static StateMachine _characterValidator = new StateMachine();

        #endregion Private Static Fields

        #region Private Fields

        /// <summary>
        /// Collection of tables that will be filled during the source code
        /// tokenization.
        /// </summary>
        private LexerTables _tables = new LexerTables();

        /// <summary>
        /// Contains preprocessing result of the original source.
        /// </summary>
        private string _preprocessedSource = string.Empty;

        #endregion Private Fields

        #region Public Properties

        /// <summary>
        /// Gets tables filled during the last source code tokenization process.
        /// </summary>
        public LexerTables Tables
        {
            get { return _tables; }
        }

        /// <summary>
        /// Gets preprocessing result of the last source code tokenization process.
        /// </summary>
        public string PreprocessedSource
        {
            get { return _preprocessedSource; }
        }

        #endregion Public Properties

        #region Constructor
        
        /// <summary>
        /// Constructs and initializes lexer.
        /// </summary>
        public Lexer()
        {
            foreach (string keyword in _keywordIndexMap.Keys) {
                _tables.Keywords.Add(_keywordIndexMap[keyword], new Keyword(keyword));
            }
            foreach (string op in _operatorIndexMap.Keys) {
                _tables.Operators.Add(_operatorIndexMap[op], new Operator(op));
            }
        }

        #endregion Constructor

        #region Public Methods

        /// <summary>
        /// Clears current lexer table contents and tokenizes specified source
        /// code. During tokenization process, lexer tables are filled with new 
        /// contents.
        /// </summary>
        /// <param name="source">Source code to tokenize.</param>
        /// <returns>True if there were no errors, false otherwise.</returns>
        public bool Tokenize(string source)
        {
            if (string.IsNullOrEmpty(source)) {
                return true;
            }

            // Clear current table contents...
            _tables.Tokens.Clear();
            _tables.Errors.Clear();
            _tables.Identifiers.Clear();
            _tables.Constants.Clear();

            _identfierIndexMap.Clear();
            _constantIndexMap.Clear();

            // Invoke preprocessor
            _preprocessedSource = Preprocessor.Preprocess(source);
                        
            // Split source code into lines.
            string [] lines = _preprocessedSource.Split(new string [] { Environment.NewLine }, StringSplitOptions.None);

            // Tokenize each line...
            for (int lineIndex = 0; lineIndex < lines.Length; ++lineIndex) {
                TokenizeLine(lineIndex, lines[lineIndex]);
            }

            return _tables.Errors.Count == 0;
        }

        #endregion Public Methods

        #region Private Methods

        /// <summary>
        /// Method used to tokenize single source code line.
        /// </summary>
        /// <param name="lineIndex">Line index.</param>
        /// <param name="line">Line content.</param>
        private void TokenizeLine(int lineIndex, string line)
        {
            if (string.IsNullOrEmpty(line))
                return;

            // Setup prefix/token trackers...
            int prefixIndex = 0;
            int prefixLength = line.Length;
            LineToken currentToken = LineToken.Unknown;
            LineToken previousToken = LineToken.Unknown;

            // Start tokenization...
            while (true)
            {
                // Get prefix content.
                string linePrefix = line.Substring(prefixIndex, prefixLength);
                // Get validation result for the prefix.
                ValidationResult result = ValidatePrefix(linePrefix);

                // If this is recognizable token...
                if (result != ValidationResult.Unknown)
                {
                    // ..fill token properties, and...
                    currentToken.Result = result;
                    currentToken.Value = linePrefix;
                    currentToken.Index = prefixIndex;
                    currentToken.LineNumber = lineIndex + 1;

                    // ...add it to lexer tables.
                    AddToken(currentToken);
                    
                    // Check if current and previous tokens are validly separated.
                    // If not, add appropriate error to the error list...
                    if (!AreTokensSeparated(previousToken, currentToken))
                        _tables.Errors.Add(new LexerError(LexerErrorCode.InvalidSeparation, currentToken.LineNumber, string.Format("Symbols '{0}' and '{1}' must be separated.", previousToken.Value, currentToken.Value)));
                                        
                    // Advance prefix from the left and break if this is last token in the line.
                    if (!AdvancePrefix(ref prefixIndex, ref prefixLength, linePrefix.Length, line.Length))
                        break;

                    // This was not last token in the line, so continue tokenization...
                    previousToken = currentToken;
                    continue;
                }

                // Prefix could not be classified, reduce prefix length.
                prefixLength--;

                // If prefix could not be reduced anymore, ...
                if (prefixLength < 1)
                {
                    // ...and left-most symbol is not whitespace, add error about unrecognized symbol.
                    if (!char.IsWhiteSpace(line[prefixIndex]))
                        _tables.Errors.Add(new LexerError(LexerErrorCode.UnexpectedSymbol, lineIndex + 1, string.Format("Symbol '{0}' is unexpected.", line[prefixIndex])));

                    // ...advance prefix from the left and break if there is nothing to tokenize.
                    if (!AdvancePrefix(ref prefixIndex, ref prefixLength, 1, line.Length))
                        break;
                }
            }
        }

        /// <summary>
        /// Applies all available validators on a specified line prefix.
        /// Returns token type for the first successful validation.
        /// </summary>
        /// <param name="linePrefix">Line prefix.</param>
        /// <returns>Token type.</returns>
        private ValidationResult ValidatePrefix(string linePrefix)
        {
            if (_keywordIndexMap.ContainsKey(linePrefix))
                return ValidationResult.Keyword;
            if (_operatorIndexMap.ContainsKey(linePrefix))
                return ValidationResult.Operator;
            if (_identifierValidator.Validate(linePrefix))
                return ValidationResult.Identifier;
            if (_octalIntegerValidator.Validate(linePrefix))
                return ValidationResult.IntegerOctal;
            if (_decimalIntegerValidator.Validate(linePrefix))
                return ValidationResult.IntegerDecimal;
            if (_hexadecimalIntegerValidator.Validate(linePrefix))
                return ValidationResult.IntegerHexadecimal;
            if (_floatValidator.Validate(linePrefix))
                return ValidationResult.Float;
            if (_doubleValidator.Validate(linePrefix))
                return ValidationResult.Double;
            if (_stringValidator.Validate(linePrefix))
                return ValidationResult.String;
            if (_characterValidator.Validate(linePrefix))
                return ValidationResult.Character;

            return ValidationResult.Unknown;
        }

        /// <summary>
        /// Advances prefix from the left by the specified amount.
        /// </summary>
        /// <param name="prefixIndex">Prefix index that will be increased.</param>
        /// <param name="prefixLength">Prefix length that will be decreased.</param>
        /// <param name="amount">Amount to advance.</param>
        /// <param name="maxLength">Maximum length of the line containing prefix.</param>
        /// <returns>True if prefix start index does not exceed last index in 
        /// the line, false otherwise</returns>
        private bool AdvancePrefix(ref int prefixIndex, ref int prefixLength, int amount, int maxLength)
        {
            prefixIndex += amount;
            prefixLength = maxLength - prefixIndex;

            return prefixIndex < maxLength;
        }

        /// <summary>
        /// Adds token to the appropriate lexer table.
        /// </summary>
        /// <param name="lineToken">Token to add.</param>
        private void AddToken(LineToken lineToken)
        {
            // Create new token.
            Token token = new Token(TokenType.Unknown, lineToken.LineNumber, -1);

            // Depending on the token type, add token to the appropriate table,
            // and assign table index to it...
            switch (lineToken.Result)
            {
            case ValidationResult.Keyword:
                {
                    token.TableIndex = (int)_keywordIndexMap[lineToken.Value];
                    token.Type = TokenType.Keyword;
                    break;
                }

            case ValidationResult.Operator:
                {
                    token.TableIndex = (int)_operatorIndexMap[lineToken.Value];
                    token.Type = TokenType.Operator;
                    break;
                }

            case ValidationResult.Identifier:
                {
                    int index;

                    // Is identifier added already...
                    if (_identfierIndexMap.TryGetValue(lineToken.Value, out index))
                    {
                        // ...yes, just assign index.
                        token.TableIndex = index;
                    }
                    else
                    {
                        // ...no, assign index and add new identifier.
                        token.TableIndex = _identfierIndexMap.Count;

                        _identfierIndexMap.Add(lineToken.Value, token.TableIndex);
                        _tables.Identifiers.Add(token.TableIndex, new Identifier(lineToken.Value));
                    }

                    token.Type = TokenType.Identifier;
                    break;
                }

            case ValidationResult.Float:
            case ValidationResult.Double:
            case ValidationResult.String:
            case ValidationResult.Character:
            case ValidationResult.IntegerOctal:
            case ValidationResult.IntegerDecimal:
            case ValidationResult.IntegerHexadecimal:
                {
                    int index;
                    
                    // Is constant added already...
                    if (_constantIndexMap.TryGetValue(lineToken.Value, out index))
                    {
                        // ...yes, just assign index.
                        token.TableIndex = index;
                    }
                    else
                    {
                        // ...no, assign index and add new constant.
                        token.TableIndex = _constantIndexMap.Count;

                        _constantIndexMap.Add(lineToken.Value, token.TableIndex);
                        _tables.Constants.Add(token.TableIndex, new Constant(lineToken.Value, GetConstantType(lineToken.Result)));
                    }

                    token.Type = TokenType.Constant;
                    break;
                }
            }

            _tables.Tokens.Add(token);
        }

        #endregion Private Methods

        #region Private Helper Methods

        /// <summary>
        /// Tests if specified token is symbol used as an escape symbol.
        /// </summary>
        /// <param name="token">Token to test.</param>
        /// <returns>True if it is escape token, false otherwise.</returns>
        private bool IsEscapeToken(LineToken token)
        {
            return _operatorIndexMap.ContainsKey(token.Value);
        }

        /// <summary>
        /// Tests if two neighboring tokens are separated validly.
        /// </summary>
        /// <param name="left">Left token.</param>
        /// <param name="right">Right token.</param>
        /// <returns>True if they are separated validly, false otherwise.</returns>
        private bool AreTokensSeparated(LineToken left, LineToken right)
        {
            return left.Index + left.Value.Length < right.Index || IsEscapeToken(left) || IsEscapeToken(right);
        }

        /// <summary>
        /// Returns constant type from the specified validation result.
        /// </summary>
        /// <param name="validationResult">Validation result.</param>
        /// <returns>Constant type.</returns>
        private ConstantType GetConstantType(ValidationResult validationResult)
        {
            switch (validationResult)
            {
                case ValidationResult.Float: return ConstantType.Float;
                case ValidationResult.Double: return ConstantType.Double;
                case ValidationResult.String: return ConstantType.String;
                case ValidationResult.Character: return ConstantType.Character;
                case ValidationResult.IntegerOctal: return ConstantType.IntegerOctal;
                case ValidationResult.IntegerDecimal: return ConstantType.IntegerDecimal;
                case ValidationResult.IntegerHexadecimal: return ConstantType.IntegerHexadecimal;
            }

            throw new Exception("Unable to determine constant type.");
        }

        #endregion Private Helper Methods

        #region Private Static Methods

        /// <summary>
        /// Static lexer initialization.
        /// </summary>
        static Lexer()
        {
            LoadKeywords();
            LoadOperators();
            InitializeValidators();
        }

        /// <summary>
        /// Loads C keywords.
        /// </summary>
        private static void LoadKeywords()
        {
            string [] keywords = Properties.Resources.Keywords.Split(new string [] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);

            for (int index = 0; index < keywords.Length; ++index) {
                _keywordIndexMap.Add(keywords[index].Trim(), index);
            }
        }

        /// <summary>
        /// Loads C operators.
        /// </summary>
        private static void LoadOperators()
        {
            string [] operators = Properties.Resources.Operators.Split(new string [] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);

            for (int index = 0; index < operators.Length; ++index) {
                _operatorIndexMap.Add(operators[index].Trim(), index);
            }
        }

        /// <summary>
        /// Initializes token type validators.
        /// </summary>
        private static void InitializeValidators()
        {
            // Setup identifier validator:
            //
            _identifierValidator.StartState = '0';
            _identifierValidator.ValidStates.Add('1');
            
            _identifierValidator.TransitionTable.Add(new TransitionTableKey('0', '_'), '1');
            _identifierValidator.TransitionTable.Add(new TransitionTableKey('0', CharacterSet.Alpha), '1');
            _identifierValidator.TransitionTable.Add(new TransitionTableKey('1', '_'), '1');
            _identifierValidator.TransitionTable.Add(new TransitionTableKey('1', CharacterSet.Alpha), '1');
            _identifierValidator.TransitionTable.Add(new TransitionTableKey('1', CharacterSet.Digit), '1');
                        
            // Setup validator for the integers with octal base:
            //
            char [] octalDigits = new char [] { '0', '1', '2', '3', '4', '5', '6', '7' };

            _octalIntegerValidator.StartState = '0';
            _octalIntegerValidator.ValidStates.Add('2');
            
            _octalIntegerValidator.TransitionTable.Add(new TransitionTableKey('0', '0'), '1');

            for (int index = 0; index < octalDigits.Length; ++index)
            {
                _octalIntegerValidator.TransitionTable.Add(new TransitionTableKey('1', octalDigits[index]), '2');
                _octalIntegerValidator.TransitionTable.Add(new TransitionTableKey('2', octalDigits[index]), '2');
            }

            // Setup validator for the integers with decimal base:
            //
            char [] decimalDigits = new char [] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
            
            _decimalIntegerValidator.StartState = '0';
            _decimalIntegerValidator.ValidStates.Add('1');
            _decimalIntegerValidator.ValidStates.Add('2');

            _decimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('0', '0'), '2');

            for (int index = 1; index < decimalDigits.Length; ++index)
                _decimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('0', decimalDigits[index]), '1');

            for (int index = 0; index < decimalDigits.Length; ++index)
                _decimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('1', decimalDigits[index]), '1');

            // Setup validator for the integers with hexadecimal base:
            //
            char [] hexadecimalDigits = new char [] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'A', 'B', 'C', 'D', 'E', 'F' };

            _hexadecimalIntegerValidator.StartState = '0';
            _hexadecimalIntegerValidator.ValidStates.Add('3');

            _hexadecimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('0', '0'), '1');
            _hexadecimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('1', 'x'), '2');
            _hexadecimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('1', 'X'), '2');

            for (int index = 0; index < hexadecimalDigits.Length; ++index)
            {
                _hexadecimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('2', hexadecimalDigits[index]), '3');
                _hexadecimalIntegerValidator.TransitionTable.Add(new TransitionTableKey('3', hexadecimalDigits[index]), '3');
            }

            // Setup validator for the single-precision floating-point literals:
            //
            _floatValidator.StartState = '0';
            _floatValidator.ValidStates.Add('S');

            _floatValidator.TransitionTable.Add(new TransitionTableKey('0', CharacterSet.Digit), '1');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('1', CharacterSet.Digit), '1');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('0', '.'), '2');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('1', '.'), '2');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('2', CharacterSet.Digit), '3');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('3', CharacterSet.Digit), '3');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('3', 'f'), 'S');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('3', 'e'), '4');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('3', 'E'), '4');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('4', '+'), '5');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('4', '-'), '5');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('4', CharacterSet.Digit), '6');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('5', CharacterSet.Digit), '6');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('6', CharacterSet.Digit), '6');
            _floatValidator.TransitionTable.Add(new TransitionTableKey('6', 'f'), 'S');

            // Setup validator for the double-precision floating-point literals:
            //
            _doubleValidator.StartState = '0';
            _doubleValidator.ValidStates.Add('3');
            _doubleValidator.ValidStates.Add('6');

            _doubleValidator.TransitionTable.Add(new TransitionTableKey('0', CharacterSet.Digit), '1');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('1', CharacterSet.Digit), '1');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('0', '.'), '2');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('1', '.'), '2');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('2', CharacterSet.Digit), '3');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('3', CharacterSet.Digit), '3');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('3', 'e'), '4');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('3', 'E'), '4');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('4', '+'), '5');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('4', '-'), '5');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('4', CharacterSet.Digit), '6');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('5', CharacterSet.Digit), '6');
            _doubleValidator.TransitionTable.Add(new TransitionTableKey('6', CharacterSet.Digit), '6');

            // Setup validator for the string literals:
            //
            _stringValidator.StartState = '0';
            _stringValidator.ValidStates.Add('2');
            
            _stringValidator.TransitionTable.Add(new TransitionTableKey('0', '\"'), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('1', '\"'), '2');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('1', '\\'), '3');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('1', CharacterSet.Any), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('3', '\"'), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('3', '\\'), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('3', 't'), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('3', 'n'), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('3', 'r'), '1');
            _stringValidator.TransitionTable.Add(new TransitionTableKey('3', 'a'), '1');

            // Setup validator for the character literals:
            //
            _characterValidator.StartState = '0';
            _characterValidator.ValidStates.Add('3');

            _characterValidator.TransitionTable.Add(new TransitionTableKey('0', '\''), '1');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('1', CharacterSet.Any), '2');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('2', '\''), '3');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('1', '\\'), '4');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('4', '\\'), '2');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('4', '\''), '2');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('4', 't'), '2');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('4', 'n'), '2');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('4', 'r'), '2');
            _characterValidator.TransitionTable.Add(new TransitionTableKey('4', 'a'), '2');
        }

        #endregion Private Static Methods
    }
}
